package org.hhchat.leetcode.dp;

/**
 * Created by HMH on 2017/4/3.
 * Sum(P) = ( Sum(nums) + target ) / 2
 *
 *
 * 有一些很酷的方法  https://discuss.leetcode.com/topic/76264/short-java-dp-solution-with-explanation
 *
 public class Solution {
    public int findTargetSumWays(int[] nums, int s) {
         int sum = 0;
         for(int i: nums) sum+=i;
         if(s>sum || s<-sum) return 0;
         int[] dp = new int[2*sum+1];
         dp[0+sum] = 1;
         for(int i = 0; i<nums.length; i++){
            int[] next = new int[2*sum+1];
             for(int k = 0; k<2*sum+1; k++){
                 if(dp[k]!=0){
                     next[k + nums[i]] += dp[k];
                     next[k - nums[i]] += dp[k];
                 }
             }
             dp = next;
         }
        return dp[sum+s];
     }
 }


 另外还有一种DFS，带存储的DFS
 public class Solution {
     public int findTargetSumWays(int[] nums, int S) {
         if (nums == null || nums.length == 0){
         return 0;
        }
        return helper(nums, 0, 0, S, new HashMap<>());
     }
     private int helper(int[] nums, int index, int sum, int S, Map<String, Integer> map){
         String encodeString = index + "->" + sum;
         if (map.containsKey(encodeString)){
            return map.get(encodeString);
         }
         if (index == nums.length){
             if (sum == S){
                return 1;
             }else {
                return 0;
             }
         }
         int curNum = nums[index];
         int add = helper(nums, index + 1, sum - curNum, S, map);
         int minus = helper(nums, index + 1, sum + curNum, S, map);
         map.put(encodeString, add + minus);
         return add + minus;
     }
 }


 */
public class code494 {
    public static class Solution {
        public int findTargetSumWays(int[] nums, int S) {
            int sum = 0;
            for (int n : nums)
                sum += n;
            if (sum % 2 != 0) {
                return 0;
            } else {
                sum /= 2;
            }
            return subSumNum(nums,sum);
        }

        private int subSumNum(int[] nums, int sum) {
            int dp[] = new int[1 + sum];
            dp[0]=1;
            for (int num : nums) {
                for (int j = sum; j >= num; j--) {
                    dp[j] += dp[j - num];
                }
            }
            return dp[sum];
        }
    }
    public static void main(String[] args){
        System.out.println(new Solution().findTargetSumWays(new int[]{1,2,7,9,981},1000000000));
    }
}
